Cryptography methods can roughly be categorized into two methods, common-key cryptography and public-key cryptography. According to common-key cryptography, the same key (private key) is used for encryption and decryption, and security is ensured by preventing the private key from being known to a third person, who is neither a transmitter nor receiver. According to public-key cryptography, different keys are used for encryption and decryption, respectively, and the key for encryption (public key) is made public, but the key for decrypting the encrypted text (private key) is secret, known only to the receiver, and thereby security is ensured.
Among techniques employed in the field of cryptography, there is a technique referred to as cryptanalysis. Cryptanalysis is a technique used for estimating secret information such as a private key or the like from accessible information such as the encrypted texts or the like, and has a wide variety of methods. Among them, there is a method referred to as a side channel attack method that has attracted attention recently. The side channel attack method was invented by Paul Kocher in 1998, and in it electrical power consumption data, noise, processing time period, and the like obtained when various data is input to the cryptographic processor mounted on a smart card or the like are collected and analyzed in order to estimate the key information in the cryptographic processor. It is known that the use of the side channel attack makes it possible to estimate the private keys in cryptographic processors regardless of whether the cryptography method is the common-key cryptography or the public-key cryptography.
The side channel attack includes a timing attack, by which processing time periods are measured and analyzed, a power analysis attack, by which power consumption is analyzed, and an electromagnetic-wave analysis attack, which uses noise, etc. Countermeasures are needed in particular against power analysis attacks and electromagnetic-wave analysis attacks because they are powerful attacking/analyzing methods. The power analysis attack and the electromagnetic-wave analysis attack are different from each other in measurement targets and measuring methods, but are the same in the essential analysis methods and countermeasures that can be used against them. Accordingly, this document describes the power analysis attack as a representative of all those attacking methods.
There are two types of power analysis attacks, a single power analysis attack (referred to as SPA hereinafter) and a differential power analysis attack (referred to as DPA hereinafter). SPA estimates the private key from characteristics of single power consumption data from the cryptographic processor, and DPA estimates the private key by analyzing the difference between many pieces of power consumption data.
Non Patent Document 1 (referred to as Kocher99 hereinafter) describes estimation methods using SPA and DPA and targeting common-key cryptographies such as DES, AES, and the like.
Non Patent Document 2 (referred to as Messerges99 hereinafter) and Non Patent Document 3 (referred to as Coron99 hereinafter) describe estimation methods using SPA and DPA targeting public-key cryptographies such as RSA cryptography, elliptic curve cryptography, and the like.
Today, among public-key cryptographies, RSA cryptography is used normally. Security provided by RSA cryptography is based on the difficulty of the prime factorization program, and this cryptography was proposed by R. Rivest, A. Shamir and L. Adleman in 1977.
The fundamental algorithms of RSA cryptography are as below.C=Me mod N  (1)M=Cd mod N  (2)
In the above algorithms, M represents a clear text message, C represents an encrypted text, (e, N) represents a public key, (d, N) represents a private key, and mod N represents a remainder of N.
In RSA cryptography, large integers such as those equal to or greater than 1024 bits are used for M, C, e, d, N, etc. Thus, an RSA cryptography device has to be implemented by combining simple operations such as those performed by a multiplier or an adder. In particular, the processes of the raising portions (exponential portions) have to be repeated in accordance with the value of the exponent, and multipliers and adders have to be controlled. The Binary method is the most representative method for this process. In the Binary method, an exponent (such as n-bit private key d for example) is expressed in binary (d=dn-1dn-2 . . . d1d0), and the raising operation for decryption is performed using the following expression.Cd=(( . . . ((Cdn-1)2*Cdn-2)2* . . . )2*Cd1)2*Cd0  (3)
In the above expression, remainder operations are performed in all the terms, and thus they are omitted. Also, because Cdi is 1 when di=0, calculations are often skipped so as to speed up the process. In such a case, the multiplication of C is sometimes performed, sometimes unperformed by di=0/1. The side channel attack targeting the RSA takes advantage of this characteristic. For example, performing multiplication causes a multiplier to operate so as to increases the power consumption, but when a multiplier does not operate, the total power consumption remains low. This makes it possible to measure 0/1 of key d by measuring the power consumption. This is referred to as the SPA (Simple Power Analysis) attack. There are other methods based on the SPA, including the DPA (Differential Power Analysis) attack, which statistically derives these characteristics from plural power consumption waveforms, an EM (Electro-Magnetic) attack, which measures electromagnetic wave noise, not power consumption, from a multiplier so as to use the measurement result for attacking, and others.
A generally employed countermeasure against the side channel attacks targeting the RSA is to add random number elements to values being calculated (intermediate values) and to exponents in order to derange the power consumption and noise so that the measurement by attackers cannot derive the key. In particular, it is known that adding random number elements to exponents makes it difficult to identify keys.
A fundamental format for a counter measurement of adding random number elements to exponents is a method referred to as Exponent Splitting disclosed by Non Patent Document 1 below. This method divides key d into two terms as represented by expression (4) below by using private key d and random number r, and calculates the expression (5) so as to make it difficult to analyze private key d.d=d′+r  (4)M=Cd′*Cr mod N  (5)
Also, in non Patent Document 5 (referred to as Ciet-Joye, hereinafter), the above expressions are modified so as to introduce a divisional expression, as below.d=d0*r+d1  (6)
A method of making it difficult to analyze private key d by using random numbers by calculating expression (7) below is proposed.M=(Cr)d0*Cd1 mod N  (7)
Further, Ciet-Joye also proposes the used of a method referred to as Shamir's Trick, disclosed by non Patent Document 6, in which the products of plural modular-exponentiation operations are calculated at a high speed (hereinafter, referred to as Ciet-Joye+ST).
Shamir's Trick is a method by which, for example, very large integers such asz=xa*yb  (8)can be calculated efficiently.
When a generally employed Binary method is used, xa and yb have to be calculated separately, and thus this method requires twice as much calculation as xa, as shown in expression (9) below.xa=(( . . . ((xan-1)2*xan-2)2* . . . )2*xa1)2*xa0 yb=(( . . . (ybn-1)2*ybn-2)2* . . . )2*yb1)2*yb0z=xa*yb  (9)
By contrast, Shamir's Trick results in table (10) below of four elements predetermined by ai and bi.T[ai,bi]={1,x,y,xy}  (10)
And expression (11) below is calculated.z=(( . . . ((T[an-1,bn-1])2*T[an-2,bn-2])2* . . . )2*T[a1,b1])2*T[a0,b0]  (11)
This makes it possible to calculate z using almost the same amount of calculation as for xa.
When RSA is implemented on a smartcard or the like, mounting that is as compact and fast as possible is required because the circuit area is limited, and operating frequencies are low. Further, a smartcard is a device having a chip mounted directly on the card itself, making it very vulnerable to attacks, and thus countermeasures against side channel attacks are essential.
FIG. 1 is an exemplary configuration of a circuit that performs a modular-exponentiation operation as decryption as expressed in expression (3) above. The operational circuit for the decryption also has the same configuration (see expressions (1) and (2).
A modular-multiplication operation circuit 104 is a circuit for performing modular-multiplication operations one time. The performance cycle of the modular-multiplication operation circuit 104 is made of two cycles, the first operation cycle and the second operation cycle. Table 1 below depicts the control via a second switch 107 in each operation cycle.
TABLE 1SWITCH CONTROL OF KEY PORTION IN FIG. 1CONTROL OF SECOND SWITCH 107FIRST OPERATIONSECOND OPERATIONdi VALUECYCLECYCLE0INTERMEDIATE VALUE1(SKIP)1INTERMEDIATE VALUEC
The second switch 107 selects and outputs an intermediate value 108 held in an in-operation data register 103. A second switch 107, in the second operation cycle, outputs value 1, for skipping operations, if the value of key bit di corresponding to the current operation cycle held in a key register 105 is 0, and outputs multiplier factor C if the value of key bit di is 1.
In the modular-exponentiation operation circuit illustrated in FIG. 1, first, an input register 101 is a register for inputting the innermost term “Cdn-1” in expression (3). This value is “C” if the most significant bit value of the key “dn-1” is 1, and is “1” if that most significant bit value is zero.
The value in the input register 101 is held by the in-operation data register 103 through the input register 101 when the decryption operation starts. A first switch 102 selects and outputs the output of the input register 101 only when an operation has started, and thereafter, selects and outputs the output of the modular-multiplication operation circuit 104.
Then, in the first operation cycle, which starts immediately after the start of the operation, the second switch 107 selects and outputs the intermediate value 108, and thereby the modular-multiplication operation circuit 104 performs a squaring of “(Cdn-1)2” in expression (3) and the remainder operation for that.
In the subsequent second operation cycle, the second switch 107 outputs “1” or “C” in accordance with the value of key bit dn-2, i.e., outputs the value of “Cdn-2”, and thereby, the modular-multiplication operation circuit 104 performs the multiplication of “(Cdn-1)2*Cdn-2”, in expression (3) and the remainder operation for that. When the second switch 107 has the output “1”, the modular-multiplication operation circuit 104 does not have to perform multiplication, and the modular-multiplication operation circuit 104 is configured to output the input value as it is.
In the subsequent first operation cycle, the second switch 107 again selects and outputs the intermediate value 108 so that the modular-multiplication operation circuit 104 again performs squaring and multiplication for that. In the second operation cycle, the second switch 107 outputs “1” or “C” in accordance with the value of key bit di, i.e., outputs the value of “Cdi” so that the modular-multiplication operation circuit 104 performs the multiplication of “(Cdn-1)2*Cdn-2” in expression (3) and the remainder operation for that.
The above pair of operations of the first and the second operation cycles is repeatedly performed (n−1) times so that expression (3) is calculated.
The above modular-exponentiation operation circuit allows the prediction of the key bit by the power analysis attacks or the like because the modular-multiplication operation circuit 104 operates or does not operate in accordance with the value of key bit di.
Thus, as prior art 1 to the present invention, an RSA that has introduced Exponent Splitting is considered. In the Exponent Splitting in the above expression (5), an adder is used for adding random number elements to d. As RSA operation resources can also be used for this, the circuit scale hardly increases. The RSA operations themselves use the normal RSA circuit in FIG. 1 only twice, and the circuit scale does not increase. Thus, it can be considered that Exponent Splitting hardly increases the circuit scale. However, the RSA circuit has to be used twice, and the RSA processing time period is twice as long as cases in which no countermeasures are taken. The reduction of the processing time period is a problem.
Next, as prior art technique 2 to the present invention, there is a case where a Ciet-Joye method is implemented. In this method, random number elements d0 and d1 used in expression (7) are operated from expression (6), and accordingly, a divider circuit is required for dividing key d by random number r. A dividing circuit is very large in circuit scale. In prior art 2, modular-exponentiation operations have to be performed for three types, i.e., Cr, (Cr)d0, Cd1, and the total number of bits of r and d0 is almost the same as that of the original d, and thus the processing time is approximately 1.5 times longer than a case where countermeasures are not take (FIG. 1). That is, a dividing circuit increases in circuit scale and the processing time becomes 1.5 times longer, and thus, implementation of Ciet-Joye causes a problem of reduction both in the circuit scale and the processing time period.
Further, as prior art 3 to the present invention, there is a case of expression (11) of applying ST to Ciet-Joye. FIG. 2 illustrates an exemplary configuration of a modular-exponentiation circuit that has to correspond to prior art 3. Table 2 below depicts control rules of the second switch 107 illustrated in FIG. 2.
TABLE 2SWITCH CONTROL OF KEY PORTION IN FIG. 2CONTROL OF SECOND SWITCH 107d0id1iFIRSTSECOND OPERATIONVALUEVALUEOPERATION CYCLECYCLE00INTERMEDIATE VALUE1(SKIP)01INTERMEDIATE VALUECr10INTERMEDIATE VALUEC11INTERMEDIATE VALUECr+1
In FIG. 2, portions denoted by the same numerical symbols as in FIG. 1 have the same functions as in FIG. 1.
In FIG. 2, a division circuit 202 stores, in a quotient register 203 and a remainder register 204, quotient d0 and remainder d1 obtained respectively by dividing key d stored in the key register 105 by random number r stored in a random number register 201.
In prior art 3, on the basis of the relationship between expression (7) and (8), ai and bi in expression (10) correspond to d0i, and d1i, and x, y, and xy in expression (10) correspond to Cr, C, and Cr*C=Cr+1. As a result of this, in prior art 3, the table values below expressed by expression (10)T[d0i,d1i]={1,Cr,C,Cr+1}  (12)are calculated when the operation starts, and are held in a multiplier-factor table memory 205 illustrated in FIG. 2.
On the basis of the above relationship, the operation of expression (7) expressed by expression (11) can be realized by repeating squaring and multiplication similarly to the case of expression (3). Accordingly, similarly to the case of FIG. 1, the second switch 107 in the circuit in FIG. 2 selects and outputs the intermediate value 108 held in the in-operation data register 103 in the first operation cycle so as to make the modular-multiplication operation circuit 104 perform squaring, and selects and outputs the value in the multiplier-factor table memory 205 based on expression (12) or table 2 in accordance with the combination of the value of quotient bit value d0i held in the quotient register 203 and the remainder bit value d1i of the key held in the remainder register 204 so as to make the modular-multiplication operation circuit 104 perform multiplication.
In prior art 3, each value in {C, Cr Cr+1} has to be calculated and set in the multiplier-factor table memory 205. This logic is complicated; however, once each value has been set, the processing time period can be reduced almost as much as in the case were there are no countermeasures in FIG. 1. That is, the switching mechanism of the multiplier-factor table memory 205 increases in addition to the addition of the division circuit 202 in view of circuit scale, and the processing time becomes almost the same as in the case where there are no countermeasures. Accordingly, when Ciet-Joye+ST is implemented, the reduction in circuit scale is a problem.
Security provided by the methods of prior arts 1 through 3 is sufficiently high (said to be a security of approximately 160 bits) as to be implemented on software (firmware) of the RSA. Conversely, security by these methods is too high to implement the RSA in a hardware manner, and thus it is desirable to realize smaller and faster implementation even at a cost of a slight drop in security.
As a countermeasure against this, a case where ST is simply applied to prior art 1 is considered. In this method, the RSA operation portion in expression (5) in prior art 1 is performed by a switching of tables. In other words, FIG. 3 illustrates an exemplary configuration of a modular-exponentiation corresponding to conventional technique 1+ST method, and Table 3 below is a table illustrating the rules of controlling the second switch 107 in FIG. 3.
TABLE 3SWITCH CONTROL OF KEY PORTION IN FIG. 3
In FIG. 3, portions denoted by the same numerical symbols as in FIG. 1 have the same functions as in FIG. 1.
In FIG. 3, a subtractor circuit 301 obtains key d′ by subtracting random number r held in random number register 201 from key d held in the key register 105 on the basis of expression (4), and stores obtained key d′ in a key register 302.
Also, according to the 1+ST method, which is a conventional technique, on the basis of expressions (5) and (8), ai and bi in expression (10) correspond to d′ and r. x, y and xy in expression (10) correspond to C, C, and C*C=C2. As a result of this, in conventional technique 3, the respective values that correspond to the table values expressed by expression (10), i.e., the following expression (13):T[d′,r]={1,C,C,C2}  (13)are calculated when the operation starts, and the results are stored in the multiplier-factor table memory 205 in FIG. 3. The second and third terms are both “C”, and accordingly the value that is actually operated is a single value, i.e., “C2”, and values to be stored are two values, i.e., “C” and “C2”.
On the basis of the above, the operation of expression (5) expressed by expression (11) is realized by repeating squaring and multiplication similarly to the case of expression (3). Accordingly, similarly to the case of FIG. 1, the second switch 107 in the circuit in FIG. 3 selects and outputs the intermediate value 108 held in the in-operation data register 103, and thereby makes the modular-multiplication operation circuit 104 perform squaring, and in the second operation cycle, the second switch 107 selects and outputs a value in the multiplier-factor table memory 205 on the basis of expression (13) or table 3 in accordance with the combination of key bit value d′i held in the key register 302 and random number bit value ri held in the random number register 201.
The 1+ST method, which is a conventional technique, holds only {C, C2} on the multiplier-factor table memory 205, and a simple logic can be used for setting values on a table. The processing speed can be as high as in the case where no countermeasures are taken against attack. However, in this method, many of the random number elements added by Exponent Splitting are cancelled by ST, and only 1 bit each of a randomness property is effective for the exponential portion and intermediate value portion. Accordingly, the 1+ST method involves a problem wherein it does not have effective countermeasures against attack.
Below is a list of prior art examples referred to in the above background art.
Non Patent Document 1:
    Paul Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis,” in proceedings of Advances in Cryptology-CRYPTO'99, Lecture Notes in Computer Science vol. 1666, Springer-Verlag, 1999, pp. 388-397Non Patent Document 2:    Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan, “Power Analysis Attacks of Modular Exponentiation in Smartcards”, Cryptographic Hardware and Embedded Systems (CHES'99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 144-157Non Patent Document 3:    Jean-Sebastien Coron “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded Systems (CHES'99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 292-302, 1999Non Patent Document 4:    C. Clavier and M. Joye, “Universal Exponentiation Algorithm: A First Step towards Provable SPA-Resistance”, CHES'01, LNCS 2162, Springer-Verlag, 2001, 300-308, 2001Non Patent Document 5:    M. Ciet and M. Joye “(Virtually) Free randomization techniques for elliptic curve cryptography,” Information and Communications Security (ICICS 2003), LNCS2836, pp. 348-359, Springer-Verlag, 2003.Non Patent Document 6:    El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (1985) 469-472